//
// Created by REEJI2219 on 2024-08-08.
//
#include "linkList.h"
#include <iostream>
Node::Node(ElemType data){
   this->data = data;
   this->next = nullptr;
}
Node::~Node() {
   this->data=0;
}

ElemType Node::getData() {
   return this->data;
}

void Node::addNext(Node* node) {
   this->next = node;
}
Node *Node::getNext() {
   return this->next;
}
LinkList::LinkList(){
   this->header = nullptr;
}
bool LinkList::take(ElemType *data) {
   if(this->header==nullptr) {
      return false;
   }
   *data = this->header->getData();
   if(this->header->getNext()) {
      this->header=this->header->getNext();
   }else {
      this->header=nullptr;
   }
   return true;
}
Node *LinkList::traval(Node *node) {
   //最后一个节点
   if(!node->getNext()) {
      return node;
   }
   Node *nextNode = traval(node->getNext());
   nextNode->addNext(node);
   node->addNext(nullptr);
   return node;
}
bool LinkList::traval() {
   Node *head = header;
   while (head->getNext()) {
      head = head->getNext();
   }
   traval(header);
   header = head;
}
bool LinkList::traval2() {
   Node *pre=header;
   if(!pre) {
      return false;
   }
   Node *current = pre->getNext();
   if(!current) {
      return true;
   }
   pre->addNext(nullptr);
   while (current->getNext()) {
      Node *next = current->getNext();
      current->addNext(pre);
      Node *tmp =current;
      current = next;
      pre=tmp;
   }
   current->addNext(pre);
   header=current;
   return true;
}
LinkList::~LinkList() {
   Node* tmp = header;
   while (tmp->getNext()!=nullptr) {
      Node* next = tmp->getNext();
      //逐个去释放内存
      delete tmp;
      tmp = next;
   }
   header=nullptr;
}


bool LinkList::append(ElemType data) {
   Node* tmpNode = new(std::nothrow) Node(data);
   if(tmpNode==nullptr) {
      return false;
   }
   if(header==nullptr) {
      header=tmpNode;
   }else {
      Node *tmp = header;
      while (tmp->getNext()!=nullptr) {
         tmp = tmp->getNext();
      }
      tmp->addNext(tmpNode);
   }
   return true;
}
bool LinkList::remove(int i, ElemType *data) {
   //找到当前节点
   Node* preNode = header;
   //找到当前节点
   for(int j=0;j<i-1;j++) {
      preNode=preNode->getNext();
      //链表长度<i ,直接返回失败
      if(preNode==nullptr) {
         return false;
      }
   }
   Node* currentNode = preNode->getNext();
   *data = currentNode->getData();
   preNode->addNext(currentNode->getNext());
   delete currentNode;
}

bool LinkList::get(int i, ElemType *data) {
   Node* tmp = header;
   for(int j=0;j<i;j++) {
      tmp = tmp->getNext();
      if(tmp==nullptr) {
         return false;
      }
   }
   *data = tmp->getData();
   return true;
}
bool LinkList::insert(int i, ElemType data) {
   Node* tempNode = new(std::nothrow) Node(data);
   if(tempNode==nullptr) {
      return false;
   }
   if(i==0) {
      tempNode->addNext(header);
      header=tempNode;
   }else {
      Node* preNode = header;
      //为什么是i-1,因为preNode = preNode->getNext()会向后进行了一步
      for(int j=0;j<i-1;j++) {
         preNode = preNode->getNext();
         if(preNode==nullptr) {
            return false;
         }
      }
      tempNode->addNext(preNode->getNext());
      preNode->addNext(tempNode);
   }
   return true;
}
void LinkList::printList() {
   Node* tmp = header;
   while (tmp->getNext()!=nullptr) {
      printf("%d ",tmp->getData());
      tmp=tmp->getNext();
   }
   printf("%d \n",tmp->getData());
}

/**
 * 将a,b链表拼接成c,同时保证不添加新的空间，时间复杂度为o(n)
 * 核心思路
 * 设置三个指针 a，b，c
 * a为a链表的头节点，b为b链表的头结点，c为c链表的头结点。被选中的向后移动一位，形成新的头
 * 1、选择合适的头节点 （a,b）中小的
 * 2、lc的头结点设置为c。
 * 3、判断a，b中小的，小的被选中，添加到c的后续，同时被选中的向后移动一位，形成新的头
 * 4、c向后移动一位，就是移动到新添加的节点
 * 5、循环3、4步骤，直到a或者b没有后续节点
 * 6、c直接添加后续不为空的链表
 * @param la a链表
 * @param lb b链表
 * @param lc c链表
 */
void LinkList::margeList(LinkList *la, LinkList *lb, LinkList *lc) {
   Node *aHead = la->header;
   Node *bHead = lb->header;
   Node *cHead = nullptr;
   //取小的当做首节点
   if(aHead->getData()<bHead->getData()) {
      cHead = aHead;
      aHead = aHead->getNext();
   }else {
      cHead = bHead;
      bHead = bHead->getNext();
   }
   //赋值给lc的头部
   lc->header=cHead;
   //当前节点都存在
   while (aHead&&bHead) {
      //谁小取谁的
      if(aHead->getData()<bHead->getData()) {
         cHead->addNext(aHead);
         //取了赋值为下一个，为下一次做准备
         aHead=aHead->getNext();
      }else {
         cHead->addNext(bHead);
         bHead=bHead->getNext();
      }
      //此时可能是a，也可能是b
      cHead=cHead->getNext();
   }
   if(aHead) {
      cHead->addNext(aHead);
   }else {
      cHead->addNext(bHead);
   }
}




